ALDS1_10_C: Longest Common Subsequence

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;

// Q034 最長共通部分列 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("abcbdab");
            WillReturn.Add("bdcaba");
            WillReturn.Add("abc");
            WillReturn.Add("abc");
            WillReturn.Add("abc");
            WillReturn.Add("bc");
            //4
            //3
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        for (int I = 1; I <= InputList.Count - 1; I += 2) {
            int LCSLength = DeriveLCSLength(InputList[I], InputList[I + 1]);
            Console.WriteLine(LCSLength);
        }
    }

    static int DeriveLCSLength(string pStr1, string pStr2)
    {
        int UB_X = pStr1.Length - 1;
        int UB_Y = pStr2.Length - 1;

        int[,] BanArr = new int[UB_X + 1, UB_Y + 1];

        // 範囲外なら0、範囲外でなければ、配列の値を返す
        Func<int, int, int> GetFunc = (pX, pY) =>
        {
            if (pX < 0 || pY < 0) return 0;
            return BanArr[pX, pY];
        };

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {

                // 一致したら左上の値+1
                if (pStr1[X] == pStr2[Y]) {
                    BanArr[X, Y] = GetFunc(X - 1, Y - 1) + 1;
                }
                else { // 不一致なら、左と上での最大値
                    int MaxVal = Math.Max(GetFunc(X - 1, Y), GetFunc(X, Y - 1));
                    BanArr[X, Y] = MaxVal;
                }
            }
        }
        return BanArr[UB_X, UB_Y];
    }
}

解説

最長共通部分列の長さ[文字列1をどこまで見たか , 文字列2をどこまで見たか]
をDPで更新してます。